class Solution
{
public:
    int minFlipsMonoIncr(string s)
    {
        int n = s.size();
        vector<int> leftOne(n);
        vector<int> rightZero(n);
        leftOne[0] = s[0] == '1';
        for (int i = 1; i < n; ++i)
        {
            if (s[i] == '1')
            {
                leftOne[i] = leftOne[i - 1] + 1;
            }
            else
            {
                leftOne[i] = leftOne[i - 1];
            }
        }
        rightZero[n - 1] = s[n - 1] == '0';
        for (int i = n - 2; i >= 0; --i)
        {
            if (s[i] == '0')
            {
                rightZero[i] = rightZero[i + 1] + 1;
            }
            else
            {
                rightZero[i] = rightZero[i + 1];
            }
        }
        int minFilp = rightZero[0];
        for (int i = 0; i < n - 1; ++i)
        {
            minFilp = min(minFilp, leftOne[i] + rightZero[i + 1]);
        }
        minFilp = min(minFilp, leftOne[n - 1]);
        return minFilp;
    }
};